package hah;

import java.util.LinkedList;
import java.util.Stack;

public class isValidPreTree {
    /*
    "=="是判断两个变量或实例是不是指向同一个内存空间。
    "equals"是判断两个变量或实例所指向的内存空间的值是不是相同。
    * */
    public boolean isValidSerialization(String preorder) {
        /*这个解法的思路其实和自己写的差不多，但是自己没有用到LinkedList作为stack，导致操作变得繁琐，
        并且没有用while循环对stack中所有满足条件的 数## 替换成# 导致最终没做出来*/
        LinkedList<String> stack=new LinkedList<>();
        for (String s:preorder.split(",")){
            stack.push(s);
            while (stack.size()>=3
                    && stack.get(0).equals("#")
                    && stack.get(1).equals("#")
                    && !stack.get(2).equals("#")){
                stack.pop();
                stack.pop();
                stack.pop();
                stack.push("#");
            }
        }
        return stack.size() == 1 && stack.pop().equals("#");
    }
    /*public boolean isValidSerialization(String preorder) {
        //写了大半天，不好使！！！！
        String[] char1= preorder.split(",");
        char[] chars=new char[char1.length];
        for (int i=0;i<chars.length;i++){
            char c=char1[i].toCharArray()[0];
            if (c=='#'){
                chars[i]=c;
            }else {
                int j=Integer.parseInt(char1[i]);
                chars[i]=(char)j;
            }
        }
        int len= chars.length;
        if(len==1&&chars[0]=='#'){
            return true;
        }
        if(len<3){
            return false;
        }
        if (chars[len-1]!='#'||chars[len-2]!='#'){
            return false;
        }
        Stack<Character> stack=new Stack<>();
        int i=0;

        while(i<=len-2){
            if (chars[i]!='#'&&chars[i]!=','){
                stack.push(chars[i]);
                i++;
            }else if (chars[i]=='#'){
                if (chars[i+1]=='#'){
                    if(stack.isEmpty()){
                        return false;
                    }
                    stack.pop();
                    if(stack.isEmpty()&&i+1==len-1){
                        return true;
                    }
                    if(stack.isEmpty()&&i+1!=len-1){
                        return false;
                    }
                    if (stack.peek()=='#'){
                        stack.pop();
                        stack.pop();
                        if (stack.isEmpty()){
                            return true;
                        }
                        stack.push('#');
                    }else {
                        stack.push('#');
                    }
                    i+=2;
                }else {
                    stack.push('#');
                    i+=1;
                }
            }
        }
        if (stack.pop()=='#'&&stack.pop()=='#'&&stack.pop()!='#'){
            return true;
        }else {
            return false;
        }
    }*/

    public static void main(String[] args) {
        String test="9,#,93,#,9,9,#,#,#";
        boolean validSerialization = new isValidPreTree().isValidSerialization(test);
        System.out.println(validSerialization);
    }
}
